\chapter{文件恢复工具的设计}

\section{总体设计}
正如上一章对YAFFS2介绍的那样，在定时被动垃圾回收抹除所有的无效chunk之前，NAND上依然保存着被修改或删除
前的文件内容。\yaffsrecover 最初的目标是尽最大可能恢复这些内容。准确地说，\yaffsrecover 能够
尽力恢复文件的所有历史版本，其中历史版本是指以一个历史文件头chunk为当前头chunk的文件版本。恢复功能需要读取NAND镜像文件、分析
YAFFS2文件系统的chunk结构、整理属于不同文件的chunk以及一个恢复算法。作为文件恢复工具，\yaffsrecover 提供
一套工具链，能够采集Android手机的NAND镜像、读取NAND芯片的OOB信息并最终完成恢复工作。工具链的工作方式
见下图：

\begin{center}
\includegraphics[width=\textwidth]{diagrams/main_structure.eps}
\captionof{figure}{\yaffsrecover 工具链结构图}
\end{center}

这一工具链中，OOB提取工具使用Linux系统调用配合NAND驱动读取OOB信息；NAND Dump工具由\texttt{mtd-utils}
或者Android手机的bootloader提供。因此，在下文的介绍中，将略去这两个次要的部分，重点介绍\yaffsrecover 本身。

除了恢复功能外，\yaffsrecover 还能输出关于NAND镜像和YAFFS2文件系统的各种信息，包括：NAND的规格、
文件系统中的所有对象的信息、每个对象的chunk信息。这些信息有助于开展在YAFFS2文件系统，以至于其他移动设备或嵌入式设备文件系统上的去重(deduplication)、敏感信息删除或保护的工作。
%\yaffsrecover 还加入了统计，能够判断两个NAND镜像或一个NAND镜像内部内容相同的chunk并进行记录。 

下图展示了\yaffsrecover 的模块结构：

%-----Begin of structure diagram-----

\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{命令行界面 / 图形前端}\\
\hline
%文件恢复算法 & 文件chunk组织可视化模块 & 统计模块\\
\multicolumn{3}{|c|}{文件恢复算法}\\
\hline
\multicolumn{3}{|c|}{文件chunk组织索引}\\
\hline
\multicolumn{3}{|c|}{Chunk解析器}\\
\hline
\multicolumn{3}{|c|}{NAND模拟层}\\
\hline
\end{tabular}
\captionof{figure}{\yaffsrecover 模块结构图}
\renewcommand{\arraystretch}{1}
\end{center}
%-----End of structure diagram-----

\subsection{设计目标}
\yaffsrecover 是一个面向Android智能手机的文件系统分析工具，设计上对方案有如下要求：
\begin{itemize}
\item 提供一套完整的，从提取到分析YAFFS2文件系统的工具链；
\item 能够适应各种型号的NAND芯片；
\item 能够对异常卸载的YAFFS2文件系统做出正确的响应；
\item 能够最大可能地恢复文件的历史版本或者被删除的文件；
\item 有良好的用户界面。
\end{itemize}


\subsection{结构及描述}
下面对\yaffsrecover 的每一个模块进行描述：
\subsubsection{NAND模拟层}
NAND模拟层负责读取NAND镜像文件，并且给上层模块提供NAND页（也就是在默认设置下的YAFFS2chunk）的读写
接口。该层负责了所有NAND硬件应当完成的工作，如硬件ECC检查和OOB读写等。由OOB提取工具提取出的OOB
布局信息就是提供给该层使用的。

\subsubsection{Chunk解析器}
该模块负责解析两部分信息：
\begin{itemize}
\item chunk的元信息，如chunkID和objectID；
\item （若该chunk是文件头chunk）文件的元信息，如文件名和父目录。
\end{itemize}

恢复算法直接依赖于该模块解析出的信息。
\subsubsection{文件chunk组织索引}
为了使文件恢复、文件系统分析等工作更有执行效率，\yaffsrecover 在扫描所有chunk后将它们组织到此模块下。
该模块将chunk按照所属的对象进行分类，并且按照chunk创建的时间进行排序。它支持快速按objectID查找对象。单一文件
恢复算法可以直接运行在查找返回的结果上。

\subsubsection{文件恢复算法}
文件恢复算法是\yaffsrecover 的核心，它接受一组按创建时间排序的属于同一对象的chunk作为输入，并将
最大可能恢复的该对象的所有历史版本作为输出。本文将在后面的章chunk对这个算法进行详细描述。

%\subsubsection{文件chunk组织可视化模块}
%该模块负责为前端提供文件的chunk的结构信息，便于对单个文件的内容进行分析。


%\subsubsection{统计模块}
%该模块的功能如下：
%\begin{itemize}
%\item 统计可恢复的chunk的数量以及大小；
%\item 计算文件系统中重复内容的数量；
%\item 计算两个NAND镜像中重复内容的数量。
%\end{itemize}

\subsubsection{用户界面}
\yaffsrecover 主程序有两个命令行前端，其中一个为参数命令行，另一个为交互式命令行。参数命令行
适用于脚本化的批量的恢复操作，而交互式命令行一方面能够输出更多的信息，让用户更精细地控制恢复的过程，
另一方面能够利用管道，与图形前端程序进行交互。

%同时，还有一个独立的图形前端程序，它通过管道与\yaffsrecover 的交互式命令行进行交互。它的主要功能是直观
%地展示文件系统 中的所有对象以及每个对象的元信息和每一chunk的信息。 

\subsection{模块间交互}
下面是在使用文件恢复功能时模块间的交互顺序图：

\begin{center}
\includegraphics[width=\textwidth]{diagrams/interaction.eps}
\captionof{figure}{\yaffsrecover 文件恢复操作的交互顺序图}

\end{center}
\section{详细设计方案}
这里介绍\yaffsrecover 的四个主要模块的设计方案：
\subsection{NAND模拟层}
采用模仿Linux设备的方式。NAND设备驱动在Linux下属于MTD（Memory Technology Device）子系统。
\yaffsrecover 采用了与MTD相同的对NAND设备的描述方式：以一个结构体来表示NAND设备，其中包含
用以维护设备参数和状态的数据字段，和用以指向读写操作的函数指针字段。与MTD不同的是读写操作的函数
实现，NAND模拟层将不从设备读写而是从已经映射入内存的一个镜像文件进行读写。

\subsection{文件chunk索引}
由于前面提到的需求，\yaffsrecover 以objectID为key，采用一棵平衡二叉树来组织所有的对象。每个
对象都包含一个链表，该链表上的元素是对象包含的所有chunk的地址。在chunk解析扫描的步骤中，这些chunk被按照
写入的时间顺序添加进链表。同时，每个对象还有一个指向自己的父对象的指针，以便于恢复目录关系。这一数据
结构如下图所示：

\begin{center}

\includegraphics[width=\textwidth]{diagrams/chunk_tree.png}
\captionof{figure}{\yaffsrecover chunk索引结构图}\label{fig:chunk_tree}

\end{center}

\subsection{文件恢复算法}
文件恢复算法接受一个YAFFS2对象在NAND上的所有chunk（包括有效的和无效的）的集合作为输入；以包含有
文件所有修改版本的集合为输出。

该算法的基本思想是按顺序模仿在该文件上进行的所有操作。算法分为两部分，其中一部分一边按时间顺序扫描所有的chunk，
一边维护一个 包含有在当前扫描状态下\emph{最新}版本的文件应该包含的chunk的集合。维护该集合的方法是：若扫描到一个
chunk的更新的版本，则说明文件内容被修改，用这个更新的chunk替换原chunk；若扫描到一个头chunk发现文件大小减少，
则从集合中删除超出新文件大小的chunk。另一部分在扫描发现一个头chunk时被调用，它会将当前维护的chunk集合重组成
文件，将集合中没有，但在文件大小范围内的chunk自动补为全0。

\subsubsection{算法描述}
\newcommand{\emptyarray}{\texttt{[]}}
\begin{center}
%\begin{algorithm}
  \begin{algorithmic}[1]
  	\Function RecoverVersions(S) \Comment {elements of S have fields: \texttt{chunkID, seq, data}}
  	\Begin
		\State R := \emptyarray
		\State K := \emptyarray
		\State Sort S with \texttt{seq} as primary key and \texttt{chunkID} as second key
		\For{\text{i:=0}}{\text{size(S)}}
			\Begin
				\If{\text{S[i].chunkID = 0}}
					\State append(R, RecoverOneVersion(K, S[i]))
				\Else
					\If{\text{K has an element k and k.chunkID = S.chunkID}}
						\State replace(K, k, S[i])
					\Else
						\State insert(K, S[i])
			\End
		\State RecoverVersions := R

	\End
  \end{algorithmic}
  \captionof{algorithm}{恢复文件的所有版本}\label{alg:1}
\end{center}
%\end{algorithm}
算法1接受的参数是经过chunk解析器扫描后的属于同一个YAFFS2对象的chunk的列表。集合$K$是最新的chunk的集合，
文件在被创建之处是没有内容的。算法第5行将这个列表按照chunk写入的时间顺序进行排序。第6行开始的循环
即按照时间顺序扫描所有的chunk。第8行判断当前扫描到的chunk是否为头chunk：若是，则调用恢复一个版本的算法，并将
恢复的结果加入包含有所有恢复版本的集合R；若否，就用当前chunk去替换K中相同chunkID的chunk。

下面是恢复一个版本的算法：

\begin{center}
  \begin{algorithmic}[1]
	\Function RecoverOneVersion(K, HdrChunk)
	\Begin
		\State F := \emptyarray
		\State F.append(HdrChunk)
		\State meta := parseHdrChunk(HdrChunk) \Comment{Meta contains the size of the file}
		\For{\text{i:=0}}{\text{size(K)}}
			\If{\text{K[i].chunkID - 1 $\times$ chunkSize $>$ meta.size}}
				\State delete(K, K[i])
		\For{\text{i:=1}}{\text{floor(meta.size/chunkSize) + 1}}
			\If{\text {K has an element k and k.id = i}}
				\State F.append(k.data)
			\Else
				\State F.append(zeroChunk)
		\State RecoverOneVersion := F
	\End
  \end{algorithmic}
  \captionof{algorithm}{恢复一个版本}\label{alg:2}
\end{center}

算法2接受集合K以及头chunk (HdrChunk)，它将根据头chunk中的元信息以及集合K中包含的文件内容恢复头chunk所代表
的文件版本F。算法第5行将头chunk中包含的信息进行解析，得到文件名和文件大小等信息。算法第6行到第8行
遍历了K，并将其中超出文件大小的chunk删除。注意本算法假设K是按引用传入的，也即对K的修改会影响到算法1
中维护的K。这样，算法1的第11-14行和算法2的6-8行就保证K是包含有在当前扫描状态下最新版本的文件应
该包含的chunk的集合。算法第9行开始的循环是为了扫描K中不连续的chunk，这些不连续的chunk之间存在这内容全为0
的“洞”。算法13行正确地写入了这些“洞”。

\subsubsection{复杂度分析}
设文件包共含有$n$个chunk，其中有$m$个头chunk。算法1的第9行，也即算法2要执行$m$次，
而算法2的复杂度是$O(|K|)$。 算法1的11行-14行要执行$n-m$次；假设采用$O(\log n)$的结构来表示$K$。
又$|K|\leq n-m$。综上，时间复杂度为：
\begin{displaymath}
m\cdot O(|K|) + (n-m)\cdot O(\log |K|) \leq O((n-m)\cdot(m+\log (n-m)) = O(m(n-m))
\end{displaymath}


